package leetcode.D200.T128;

import java.util.HashSet;
import java.util.Set;

public class Solution {
    // 一刷
    /*public int longestConsecutive(int[] nums) {
        int maxLen = 0;
        Set<Integer> set = new HashSet<>();
        for(int i=0; i<nums.length; ++i) {
            set.add(nums[i]);
        }
        for(int i=0; i<nums.length; ++i) {
            if(!set.contains(nums[i]-1)) {
                int len = 1, cur = nums[i];
                while (set.contains(cur+1)) {
                    cur++;
                    len++;
                }
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }*/

    // 二刷
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int maxLen = 0;
        for (int num : nums) {
            if (!set.contains(num+1)) {
                int cur = num, len = 1;
                while (set.contains(cur-1)) {
                    cur--;
                    len++;
                }
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }
}
